1. Field of the Invention
The present invention relates to stream scheduling method and apparatus suitable for a real time stream server.
2. Description of the Background Art
Data such as dynamic images and speeches which are to be sequentially transferred in real time are called real time stream data. A real time stream server for handling such real time stream data is required to be capable of transferring the real time stream data stored in disk devices to each client (such as a set top box or a personal computer connected with the real time stream server via a communication means) while guaranteeing the continuity in real time.
In order to meet this requirement, conventionally, the real time stream data are divided into blocks in units of a certain reproduction time or in units of a certain size and stored in disks, and then the server makes accesses to the disks periodically for each client. The scheme for storing data in division over a plurality of disks in this manner is called the striping, which is widely used conventionally.
The blocks read out from the disks are placed on a buffer memory once, and periodically transferred to the corresponding client via the communication network. In the real time stream server, timings for issuing a disk access command and a data transfer command in this operation are managed by a stream scheduling apparatus.
Also, the stream scheduling apparatus establishes a new stream channel by receiving a connection request from a client and scheduling a transfer of the real time stream data to that client. A stream channel for the transfer of the real time stream data from the real time stream server to the client which is established in this manner is called a stream.
In the stream scheduling apparatus, the timings for disk accesses and data transfers are managed using time-slots which divide each disk access period into constant time intervals as shown in FIG. 1. One disk access is to be allocated to one time-slot, and one block of the real time stream data is to be read out by one disk access. A disk access period for each stream is constant, and the disk access of each stream which is allocated to a particular time-slot will be fixedly allocated to that particular time-slot.
Consequently, by allocating the disk accesses of different streams to different time-slots, it becomes possible for a plurality of streams to utilize the stream data stored in the identical disk simultaneously. Here, however, as many time-slots as a number of connectable streams will be required within an access period with respect to one disk device.
The conventionally known multiple read out techniques for a case of striping data over a plurality of disks include a scheme for handling a plurality of disk devices virtually as a single high speed disk device as shown in FIG. 2, and a scheme for making an access to a disk device having a next block at each period as shown in FIG. 3.
In the examples of FIG. 2 and FIG. 3, the disk access of the stream of a client 0 is allocated to a time-slot 0 of each disk access period. A read out block A1 represents a block 1 of the real time stream data A. After A1 is read out, this A1 is transferred to the client 0 and processed (reproduced, for example) there in real time. Before the processing of A1 is finished, A2 is read out and transferred. In this manner, each stream is scheduled without affecting the continuity of the other stream. The stream scheduling apparatus maintains the continuity of each stream by repeating the operations of the reading of data from disks and the transfer of the read out data periodically, according to the schedule expressed in terms of such time-slots.
A number of streams that can be simultaneously connected to a single real time stream server is determined by a ratio M of a data transfer bit rate of a disk device with respect to a data reproduction bit rate and a number Ndisk of disk devices. Methods for increasing a number of connectable streams include a first method for increasing a transfer capability of the disk device and a second method for increasing a number disk devices to which the striping is applied.
In the first method, an average transfer rate is increased by shortening a seek time of the disk device and thereby shortening the response time of the disk device. In this method, a time period for one slot can be shortened, so that it is possible to increase the maximum number of streams.
The second method is divided into two types according to the scheduling scheme to be used. The first scheme is a scheme for handling a plurality of disk devices virtually as a single high speed disk device by reading out continuous blocks to be transferred to a single stream from a plurality of disk devices simultaneously, as shown in FIG. 2. The second scheme is a scheme for making an access to a disk device in which a next block is stored at each period, in which data for different streams are read out at a plurality of disk devices simultaneously, as shown in FIG. 3.
As can be seen in FIG. 2 and FIG. 3, a number of simultaneously connectable streams can be increased Ndisk times in both of these first and second schemes. Here, however, the access period (a number of time-slots) with respect to a certain single disk device for each stream is also increased Ndisk times.
In the real time stream server, as shown in FIG. 4, the response time is given by a total of a time since a connection request is received until a first disk access is started, a time required for the disk access, and a time for which data read out from the disk are stored in a buffer memory until the transfer to the client is started.
In practice, the delay time from a point of view of the user also includes a delay until the data are transferred to the client via the network and the reproduction of the transferred data is started at the client side, but this delay cannot be managed by the real time stream server, so that this delay will not be included in the response time here.
In a case where a connection request for a stream from a client newly occurred, the stream scheduling apparatus secures a vacant time-slot to which the disk access of the new stream can be allocated. At this point, in the conventional art, the disk accesses of the streams for which the connections are already established are fixed to the allocated time-slots, so that the stream scheduling apparatus secures a vacant time-slot subsequent to the time-slot at which the connection request has occurred, to which the already connected stream is not allocated, and whose turn comes around at the earliest timing.
In a case of securing a vacant time-slot by such a scheme, it is possible to make a response in a short time if vacant time-slots are evenly dispersed among the time-slots. However, in a case where the vacant time-slots are unevenly distributed as in a situation in which many streams are already connected to the real time stream server, there is a high probability for the response time to be long.
For this reason, in a case of setting a time limit for the response time in order to secure a certain amount of the response time, there is a high probability for the response time to exceed the time limit as the vacant time-slot to which the disk access can be allocated does not exist within the specified time limit. In particular, in a case of increasing the maximum number of connectable streams, there is a limit to the increase of the maximum number of connectable streams according to the first scheme of FIG. 2 described above, and the maximum response time becomes longer as the maximum number of connectable streams becomes larger according to the second scheme of FIG. 3 described above.
For example, in FIG. 3, in a case where the client 2m-1 issues the connection request to transfer the real time stream data F from the block 1, the disk access will not be made until a vacant time-slot becomes available for the disk device 1 which stores the block F1, that is, until the time-slot m-1 of the disk access period 2.
In recent years, with the real time stream server as a basic technique, a video server or a multimedia server has been developed, and the information service using such a server called a video-on-demand, multimedia-on-demand, or information-on-demand has been started.
Such an information system provides the service simultaneously to many users via client terminals connected by the network, using video and/or speech data which are the real time stream data or composite data in which the real time stream data are combined with conventional text and/or image data. In such a situation, many clients are going to be connected to the real time stream server simultaneously, and it has become an indispensable task to make the response time with respect to each client as short as possible.
As described above, conventionally, a timing of a disk access of a stream which is transferring data to a client is fixed on the time-slot, and the closest vacant time-slot has been allocated to a new stream for which a connection request is made.
Consequently, in a case where many streams are already connected to the real time stream server, when vacant time-slots are distributed unevenly, there is a high probability for requiring a long response time since a time at which the request for the real time stream data is received until the transfer of the first data block of the real time stream data is started.
Therefore, in a case of setting a time limit for the response time in order to secure a certain amount of the response time, there is a high probability for the response time to exceed the time limit as the vacant time-slot to which the disk access can be allocated does not exist within the specified time limit.